NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/sys/amiga/programmer/7271

Text File | 1996-08-05 | 8.7 KB | 175 lines

Path: soap.news.pipex.net!pipex!usenet
From: [e-mail] (Mathew Hendry)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: 680X0 -> PPC translator?
Date: Sat, 13 Apr 96 15:57:24
Organization: Private node.
Distribution: world
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: an089.du.pipex.com
X-Newsreader: TIN [AMIGA 1.3 950726BETA PL0]

Jack ([e-mail]) wrote:
: Mathew Hendry wrote:
: > Jack ([e-mail]) wrote:
: > : Mathew Hendry wrote:
: > : > Jack ([e-mail]) wrote:
: > : > : many problems aren't solvable with today's technology, but it doesn't mean
: > : > : they're not solvable with other yet-to-devised methods, now do they??
: > : >
: > : > Some may be solved by new algorithms, but no finite number of algorithms can
: > : > solve all problems. You surely can't be suggesting that your static translator
: > : > will contain an infinite number of algorithms - or one infinitely large one.
: > :
: > : hell no, the algorithm is definitly not infinite otherwise i wouldn't suggest it
: >
: > In that case, it can't work in all cases. There is an inherent indeterminacy
: > between code and data which cannot be completely resolved by ANY algorithm
: > which you may come up with. This can be proved using a variant of G÷del's
: > theorem formulated by Alan Turing.
:
: by all means, prove me wrong. be concrete and don't generalize one theorem
: on this case, please.

Er, I'm not "generalizing" the theorem - it applies directly to this situation.
Since you say in another post that you don't even know what a Turing machine
is, you clearly don't know anything about what this theorem says. So, I refer
you to:

Turing, A. M. (1937). On computable numbers, with an application to the
Entscheidungsproblem. Proceedings of the London Mathematical Society (ser. 2),
42, 230-65; a correction, 43, 544-6.

Two things are significant here:

1. Current computers are equivalent to generalised Turing machines - i.e.
anything which may be computed on a generalised Turing machine may also be
computed on a current computer (barring storage limitations) and vice versa.

2. No algorithm which can be executed on a generalised Turing machine can
completely track the logical path of every other possible algorithm in all
situations.

When these two points are applied to the problem of static program
translation, it becomes clear that, since no algorithm can completely track
the logical path followed by all programs in all situations, no algorithm can
reliably make the distinction between code and data which your claims imply.

Note that the proof of this includes ALL POSSIBLE ALGORITHMS which one may
attempt to use to make the distinction - and STILL the problem is insoluble in
the general case.

: code and data can easily be distinguished, if a series of words makes sense
: as a code section it's probably code and you can make sure it is by
: deferring its translation until it is called from some place else or it
: simply makes too much sense to be random data. for example: valid
: jump/calls, references valid addresses, code instruction sequence maintained
: w/o being interrupted by some data word which doesn't make sense as code.

This vague hand-waving only allows you to get out of certain situations, not
all. You can wave your hands until they fall off and yet still never reach a
complete solution.

: what you claim suggests that not any algorithm can solve ALL situations of a
: given problem, like how many algorithms exist for adding 2 numbers. there's
: obviously one.

That is not what the theorem says at all. Clearly some classes of problem are
completely soluble algorithmically in the general case. What the theorem says
is that some classes are NOT, and static translation is one of that set of
classes. The solution of generalised Diophantine equations (which I think were
mentioned in an earlier post) is another class of problem within this set.

: your inability to deal with more complex problems prevents you from seeing a
: possible solution.

There is no possible solution. I cannot see something which doesn't exist. Can
you?

: just as human can do manual translation of the code so can an algorithm.

Obviously, for a PARTICULAR case. All the human has to do is encode those
operations which [s]he has performed as an algorithm. But clearly that
algorithm will not apply to all other programs.

If you want to make the stronger claim that a human can in principle (*)
translate ANY program accurately (and you have no way of proving this), then
it does NOT follow that an algorithm can too, because it has already been
PROVEN that an algorithm CANNOT. What follows, instead, is that humans do not
operate algorithmically, which is a very strong claim indeed.

* - in practice, a human will make errors, but we are talking about
principle here. In other words, a human may be intellectually CAPABLE of
solving the problem in the general case, even though in practice [s]he may
make mistakes, die of old age in the meantime, etc.

: > : their earthly solution, but not all secrets have been uncovered yet, the inability to solve something
: > : doesn't make it impossible to solve, there's always some way or another to solve things even in the
: > : most indirect and mysterious ways, you can't just claim they're impossible to solve just because you
: > : still hav'nt found any workable solution.
: >
: > Sorry, no matter how many "indirect and mysterious ways" you invent, the
: > problem cannot be solved algorithmically for all cases. That is a mathematical
: > truth.
:
: oh is that so, you speak as if ALL of the math secrets are discovered to you.

Of course they aren't all "discovered to me", but that is irrelevant.

: well you DON'T know that for sure. have you tried ALL possible solutions to
: solve one of your undecidable problems.

The proof INCLUDES all possible solutions. It therefore doesn't matter how
many of those particular solutions *I* currently know.

Do you have to add every pair of numbers to know that your algorithm for
adding a pair of numbers is correct? No, the fact that it is correct follows
from the construction of the number system. Likewise, the fact that a computer
cannot reliably translate all computer programs follows from the construction
of the computer.

: i'm not eliminating the impossible, oh no, some things are definitly
: impossible even to imagine. but you simply have no CONCRETE basis for your
: claim. as all the others have already submitted their ideas of impossible
: getaway situations which have successfully been dealt with by yours truely,
: i suggest you do the same to undermine my theory.

All you are doing is adding bits to your algorithm to deal with more
situations. The point is that no matter how much you add, you cannot deal
with ALL situations. Anybody can give you an example of a program which will
be broken by your translator (although at this time it is difficult to be
specific, because you haven't yet given a full description of your algorithm),
and you can come up with an enhancement which will solve that PARTICULAR
problem, but never ALL problems.

: > Great, try translating a program which in some circumstances attempts to
: > execute some of its own data. You immediately have a problem - is that portion
: > of the program code or is it data? You cannot decide, for sometimes it appears
: > to be data, and sometimes it appears to be code. This indeterminacy remains
: > even if the program contains no bugs, and remember, nearly all useful programs
: > DO contain bugs.
:
: read above paragraphs for hints of solving this simple situation.

I see nothing there which would solve it in all cases. You have made vague
claims involving "probably", "makes sense" etc. etc., fuzzy indications of
what algorithms you use to decide such things, and NO PROOF that they would
work in all situations (which of course they cannot, whatever they are).

: > You may choose to work around such problems by storing indeterminate program
: > fragments in their original form in the translated binary. But these residual
: > untranslated pieces will have to be handled on the fly when running the
: > translated program. In that case, you no longer have a static translator -
: > you have an emulator.
:
: no no no, no further run-time analysis is necessary. only static translation.

Prove it. Again, you cannot.

A program such as yours would be genuinely useful, even though it can only
work in some cases. However, your claim that it is flawless and will work in
all cases is patently false. That is what I am taking issue with.

-- Mat.